package greedy;

/**
 * @author HuWLin
 * 入门贪心算法
 * */
public class Greedy {

    /*
    * @param 传入数组
    *
    * 力扣第334题：递增的三元子序列
    * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
    * 贪心算法思路：第一个数和第二个数尽可能小，这样更方便找到第三个数字
    *
    * 来源：力扣（LeetCode）
    * 链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence
    * */
    public static boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        //长度小于3必然不是三元组
        if(n < 3){
            return false;
        }
        //first用来记住第一个数字，second用来记住第二个数字,
        //第二个数区最大值是因为，配合下面i从1开始
        int first = nums[0],second = Integer.MAX_VALUE;
        for(int i = 1;i < nums.length;i ++){

            if(second < nums[i]){
                return true;
            }else if(first < nums[i]) {
                //考虑如果第一个数小于第i个数的情况下，就把这个赋值给second
                second = nums[i];
            }else{
                //如果第i个数小于第一个数，就把数赋值给第一个
                first = nums[i];
            }
            //综合上面情况，第一个数肯定小于第二个数，优先判断第一个数小于当前数才会赋值给第二个数
        }
        return false;
    }
}
